/**
有m个人(m=100)，每个人一个号码牌(1-100) ，围成一个圆，从第一个人开始数，每数到7淘汰该人，下一个人继续从1开始计数并到7淘汰，以此类推，问最终剩下的人手里的号码牌是几?
**/

/***
1、使用环形链表。
2、末尾的处理  n

 */
class Solution {
    public int lastRemaining(int n, int m) {
       ListNode head = createCycleList(m);
        //print(head);
        ListNode handler = head;
        while( n!=1 ){
            for(int i = 1 ;i < m;i++){
                //迭代
                handler=handler.next;
            }
            //删除
            handler.next=handler.next.next;
            handler=handler.next;
            n--;
        }
    }

    class ListNode {

        public ListNode next;
        public int value;

        public ListNode(ListNode next, int value) {
            this.next = next;
            this.value = value;
        }
    }

    public ListNode createCycleList(int n) {
        ListNode head = new ListNode(null, 0);
        ListNode handle = head;
        for (int i = 1; i < n-1; i++) {
            ListNode node = new ListNode(null, i);
            handle.next = node;
            handle = handle.next;
        }
        handle.next = new ListNode(head, n-1);
        return head;
    }

    private void print(ListNode head,int n) {
        for (int i = 0; i < n; i++) {
            System.out.println(head.value);
            head = head.next;
        }
    }
  
}


